#include "stdlib.h"
#include "stdio.h"

#define MaxSize 10

typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
} SqList_sta;

typedef SqList_sta* SqList_sta_t;
/**************************************************************/
#define InitSize 10

typedef int ElemType;

typedef struct{
    ElemType *data;
    int length;
    int max;
} SqList_syn;

/**************************************************************/

typedef SqList_syn List;
typedef List* List_t;


void InitList_sta(List_t L)
{
    for(int i=0;i<MaxSize;i++)
    {
        L->data[i]=0;
    }
    L->length=0;
}

void InitList_syn(List_t L)
{
    L->data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
    L->length=0;
    L->max=InitSize;
}

int Length(List L)
{
    return L.length;
}

int LocateElem(List L,ElemType e)
{
    if(L.length==0)
        return -1;
    for(int i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}

ElemType GetElem(List L,int i)
{
    if(L.length==0)
        return -1;
    
    return L.data[i-1];
}

int ListInsert(List_t L,int i,ElemType e)
{
    if(i<1 || i>L->length+1)
        return -1;
    if(L->length >= L->max)
        return -1;
    for(int j=L->length;j>=i;j--)
    {
        L->data[j]=L->data[j-1];
    }
    L->data[i-1]=e;
    L->length++;
    return 0;
}

int ListDelete(List_t L,int i,ElemType *e)
{
    if(i<1 || i>L->length+1)
        return -1;
    *e = L->data[i-1];
    L->data[i-1]=0;
    for(int j=i;j<L->length;j++)
    {
        L->data[j-1]=L->data[j];
    }
    L->length--;
    return 0;
}

int PrintList(List L)
{
    if(L.length==0)
        return -1;
    for(int i=0;i<L.length;i++)
    {
        printf("%d ",L.data[i]);
    }
    printf("\n");
    return 0;
}

int isEmpty(List L)
{
    if(L.length==0)
        return 0;
    else
        return -1;
}

int DestroyList(List_t L)
{
    free(L);
}

/*测试函数功能*/
void testfunc(void)
{
    List LL;
    int k;

    InitList_syn(&LL);
    PrintList(LL);
    printf("is empty? %d\n",isEmpty(LL));
    ListInsert(&LL,1,1);
    ListInsert(&LL,2,2);
    ListInsert(&LL,3,3);
    ListInsert(&LL,4,4);
    ListInsert(&LL,5,5);
    printf("is empty? %d\n",isEmpty(LL));
    PrintList(LL);
    printf("insret 9 statue %d",ListInsert(&LL,9,11));
    PrintList(LL);
    ListDelete(&LL,4,&k);
    printf("delete 4 return %d\n",k);
    PrintList(LL);
    printf("now lenth is %d\n",LL.length);
    printf("Locate 3 is %d\n",LocateElem(LL,3));
    printf("%d\n",GetElem(LL,1));
}
// 2.2.3 综合应用题 01 
// 找到最小元素删除并带回值，拿最后一个值填充此位置
int work_223_1(List_t L,ElemType *e)
{
    ElemType min_val=L->data[0],min_int=0;
    if(L->length==0)
    {
        printf("the List is empty\n");
        return -1;
    }
    for(int i=0;i<L->length;i++)
    {
        if(L->data[i]<min_val)
        {
            min_val=L->data[i];
            min_int=i;
        }
    }
    *e=min_val;
    if(min_int != L->length-1) //最小元素不是最后一个
    {
        L->data[min_int]=L->data[L->length-1];
        L->data[L->length-1]=0;
    }
    else  //最小元素是最后一个
    {
        L->data[L->length-1]=0;
    }
    L->length--;
    return 0;
        
}
// 2.2.3 综合应用题 02 
// 逆序所有元素 要求O（1）空间复杂度
int work_233_2(List_t L)
{
    ElemType t;
    int p;
    if(L->length==0)
        return -1;
    for(int i=0;i<L->length/2;i++)
    {
        t=L->data[L->length-1-i];
        L->data[L->length-1-i]=L->data[i];
        L->data[i]=t;
    }
    return 0;
    
}
// 2.2.3 综合应用题 03 
// 长度n的线性表L 时间O(n)空间O(1) 删除线性表中所有值为x的元素
int work_233_3_f(List_t L,ElemType x)
{
    ElemType e;
    //时间复杂度 O(n^2)
    for(int i=0;i<L->length;i++)
    {
        if(L->data[i]==x)
        {
            ListDelete(L,i+1,&e);
        }
    }
}
int work_233_3_1(List_t L,ElemType x)
{
    int k=0,i;
    if(L->length==0)
        return -1;
    for(i=0;i<L->length;i++)
    {
        if(L->data[i]!=x)
        {
            L->data[k]=L->data[i];
            k++;
        }  
    }
    L->length=k;
    return 0;
}
int work_233_3_2(List_t L,ElemType x)
{
    int k=0,i;
    if(L->length==0)
        return -1;
    while(i<L->length)
    {
        if(L->data[i]==x)
            k++;
        else
        {
            L->data[i-k]=L->data[i];
        }
        i++;
    }
    L->length=L->length-k;
    return 0;
}
// 2.2.3 综合应用题 04 05
// 删除s~t之间的元素
int work_233_4and5(List_t L,ElemType s,ElemType t)
{
    if(L->length==0)
    {
        printf("list is empty\n");
        return -1;
    }
    if(s>t)
    {
        printf("error input\n");
        return -1;
    }
    int k=0;
    for(int i=0;i<L->length;i++)
    {
        if(L->data[i]<s||L->data[i]>t)
        {
            L->data[k]=L->data[i];
            k++;
        }
    }
    L->length=k;
    return 0;
}
// 2.2.3 综合应用题 06
// 从有序表中删除所有值重复的元素
int work_233_6(List_t L)
{
    if(L->length==0)
        return -1;
    int k=0,t=0;
    for(int i=1;i<L->length;i++)
    {
        if(L->data[i]==L->data[k])
        {
            L->data[i]=0xff;
        }
        else
        {
            k=i;
        }
    }
    for(int i=0;i<L->length;i++)
    {
        if(L->data[i]!=0xff)
        {
            L->data[t]=L->data[i];
            t++;
        }
    }
    L->length=t;
    return 0;
}
// 2.2.3 综合应用题 07
// 合并两个有序表
List_t work_233_7(List_t L1,List_t L2)
{
    if(L1->length==0)
        return L2;
    if(L2->length==0)
        return L1;
    List_t Lr=(List_t)malloc(sizeof(List));
    Lr->max=L1->length+L2->length;
    Lr->data = (ElemType *)malloc(sizeof(ElemType)*(Lr->max));
    Lr->length=0;
    List_t p; //长的
    List_t q;
    if(L1->length!=L2->length)
    {
        int max_len=L1->length>L2->length?L1->length:L2->length;
        p= (max_len==L1->length?L1:L2); //长的
        q= (max_len==L1->length?L2:L1); //短的
    }
    else
    {
        int max_len=L1->length;
        p= L1; 
        q= L2; 
    }
    int i=0,j=0,k=0,m=0;
    while(1)
    {
        if(p->data[i]<q->data[j])
        {
            Lr->data[k]=p->data[i];
            k++;
            i++;
            if(i > p->length-1)
            {
                break;
            }
        }
        else
        {
            Lr->data[k]=q->data[j];
            k++;
            j++;
            if(j > q->length-1)
            {
                break;
            }
        }
    }
    if(i==p->length) //p链遍历完毕
    {
        for(;j<=Lr->max;j++)
        {
            Lr->data[k]=q->data[j];
            k++;
        }
    }
    else            //q链遍历完毕
    {
        for(;i<=Lr->max;i++)
        {
            Lr->data[k]=p->data[i];
            k++;
        }
    }
    Lr->length=Lr->max;
    return Lr;
}


int main(void)
{
    List LL,LL_e;
    List_t LL_r;
    ElemType val;
    InitList_syn(&LL);
    InitList_syn(&LL_e);
    ListInsert(&LL,1,1);
    ListInsert(&LL,2,4);
    ListInsert(&LL,3,5);
    ListInsert(&LL,4,9);

    ListInsert(&LL_e,1,-4);
    ListInsert(&LL_e,2,9);
    ListInsert(&LL_e,3,10);
    ListInsert(&LL_e,4,10);

    PrintList(LL);
    PrintList(LL_e);
    LL_r = work_233_7(&LL,&LL_e);
    PrintList(*LL_r);
}



